//两个列表的最小索引和
//假设 Andy 和 Doris 想在晚餐时选择一家餐厅，并且他们都有一个表示最喜爱餐厅的列表，每个餐厅的名字用字符串表示。
//你需要帮助他们用最少的索引和找出他们共同喜爱的餐厅。如果答案不止一个，则输出所有答案并且不考虑顺序。 
//假设答案总是存在

//排序做法必须要使用结构体类型排序，将索引和字符串对应后一一排序
//若直接将字符串排序，则原索引也会被改变
typedef struct Restaurant {
    int index;
    char* info;
}Rest;
int Cmp(const void* p1, const void* p2) {
    return (int)(strcmp(((Rest*)p1)->info, ((Rest*)p2)->info));
}
char** findRestaurant(char** list1, int list1Size, char** list2, int list2Size, int* returnSize) {
    int i, j, sum, val, count, max;
    char** res = (char**)malloc((list1Size < list2Size ? list1Size : list2Size) * sizeof(char*));
    *returnSize = 0;
    Rest* src1 = (Rest*)malloc(list1Size * sizeof(Rest));
    Rest* src2 = (Rest*)malloc(list2Size * sizeof(Rest));
    i = j = 0;
    max = list1Size + list2Size;
    for (i = 0; i < list1Size; i++) {
        src1[i].index = i;
        src1[i].info = list1[i];
    }
    for (j = 0; j < list2Size; j++) {
        src2[j].index = j;
        src2[j].info = list2[j];
    }
    qsort(src1, list1Size, sizeof(Rest), Cmp);
    qsort(src2, list2Size, sizeof(Rest), Cmp);
    i = 0, j = 0;
    while (i < list1Size && j < list2Size) {
        val = strcmp(src1[i].info, src2[j].info);
        if (val > 0)
            j++;
        else if (val < 0)
            i++;
        else {
            sum = src1[i].index + src2[j].index;
            if (sum < max) {
                max = sum;
                *returnSize = 0;
                res[(*returnSize)++] = src1[i].info;
            }
            else if (sum == max)
                res[(*returnSize)++] = src1[i].info;
            i++;
            j++;
        }
    }
    free(src1);
    free(src2);
    src1 = src2 = NULL;
    return res;
}

